Usually, DSP (digital signal processors) and other processors have an arithmetic logic operation device (arithmetic logic unit: ALU) for performing arithmetic operations (addition, multiplication, etc.) and logic operations (bit inversion, bit shift, etc.). The various types of arithmetic operations performed by an ALU are based on the addition operation, and they make use of the addition operation results. Usually, the ALU adder has a function for detecting whether overflow occurs in the addition result. When overflow is detected, the ALU performs processing to forcibly correct the output to a prescribed value (such as positive maximum value or a negative minimum value).
Japanese Kokai Patent Application No. Hei 7-182141 describes a technology pertaining to an operation device that performs said overflow correction. The prior art of adders having an overflow detecting function will be explained in the following.
For the adder to be explained below, 40-bit signals [a0, . . . a39] and [b0, . . . b39] as well as carry signal CIN to the least significant digit (first digit) are input, and a 40-bit signal [s0, . . . s39] is output as the addition result. Also, said adder has two operating modes, that is, a 40-bit mode and a 32-bit mode. In addition, it has a conventional mode and a dual mode in each of said operating modes. In the 40-bit mode, the adder performs addition operations with the 40th digit as the most significant digit. Also, it outputs overflow detection signal OVF as the signal indicating the presence/absence of overflow in the addition operation, with the 40th digit taken as the sign digit. On the other hand, in the 32-bit mode, the addition operation is performed with the 32nd digit as the most significant digit. In this case, said overflow detection signal OVF is output as the signal indicating the presence/absence of overflow in the addition operation with the 32nd digit taken as the sign digit.
In the conventional mode, the adder performs only the addition operation from the first digit to the most significant digit (that is, the 40th digit in the 40-bit mode, or the 32nd digit in the 32-bit mode). In the dual mode, the addition operation from the first digit to the 16th digit and the addition operation from the 17th digit to the most significant digit are performed in parallel. In the dual mode of the adder, carry signal CIN for the addition operation of the less significant side (1st-16th digits) is input as the carry to the least significant digit, and carry signal Cdual is input for the addition operation of the more significant side (17th to most significant digits). Also, overflow detection signal OVF16 is output as the signal indicating the presence/absence of overflow in the addition operation of the less significant side, with the 16th digit taken as the sign digit.
FIG. 12 is a block diagram illustrating an example of the constitution of the circuit for generating overflow detection signal OVF16 of the less significant 16 digits in the dual mode in said adder. The circuit shown in FIG. 12 has the following circuits: carry generating signal output circuits 1, . . . 4, 11, 12, carry propagation signal output circuits 5, . . . 10, selectors 13 and 14, carry select adder (hereinafter to be referred to as CSA) 15 and exclusive-NOR circuit 16.
Overflow detection signal OVF16 is a signal that is “0” when overflow occurs and is “1” when overflow does not occur in the addition result for input data in the two's complement form, with the 16th digit taken as the sign digit in the dual mode, and it is represented by the following operation:
[Mathematical Equation 1]OVF16= c14⊕c15  (1)
Here, carry signal ci (where i represents an integer in the range of 0-39) indicates the carry from the (i+1)th digit to the (i+2)th digit. In the circuit shown in FIG. 12, when said overflow detection signal OVF16 is computed, carry signals c11 and c15 are first computed using the carry look-ahead system. In the circuit shown in FIG. 12, the portion composed of carry generating signal output circuits (1-4, 11, 12), carry propagation signal output circuits (5-10) and selectors (13, 14) is the carry look-ahead circuit that generates carry signals C11 and C15. This carry look-ahead circuit generates the intermediate carry generating signal and the carry propagation signal in two separate steps, and finally obtains carry signals (C11, C15).
Carry signals C11 and C15 are represented by the following equations, respectively:
                    [                  Mathematical          ⁢                                          ⁢          equation          ⁢                                          ⁢          2                ]                                                                      c          ⁢                                          ⁢          11                =                  p          ⁢                                          ⁢          11          ×          p          ⁢                                          ⁢          10          ⁢                                          ⁢          …          ×          p          ⁢                                          ⁢          0          ×          CIN                                    (        2        )                                                          ⁢                              p            ⁢                                                  ⁢            11            ×            p            ⁢                                                  ⁢            10            ×            …            ×            p            ⁢                                                  ⁢            1            ×            g            ⁢                                                  ⁢            0                    +                                                                                              ⁢                  p          ⁢                                          ⁢          11          ×          p          ⁢                                          ⁢          10          ×          …          ×          p          ⁢                                          ⁢          2          ×          g          ⁢                                          ⁢          1                                                                                              ⁢                  ⋮          +                                                                                              ⁢                              p            ⁢                                                  ⁢            11            ×            g            ⁢                                                  ⁢            10                    +                                                                                              ⁢                  g          ⁢                                          ⁢          11                                                                              c          ⁢                                          ⁢          15                =                              p            ⁢                                                  ⁢            15            ×            p            ⁢                                                  ⁢            14            ⁢                                                  ⁢            …            ×            p            ⁢                                                  ⁢            0            ×            CIN                    +                                    (        3        )                                                          ⁢                              p            ⁢                                                  ⁢            15            ×            p            ⁢                                                  ⁢            14            ×            …            ×            p            ⁢                                                  ⁢            1            ×            g            ⁢                                                  ⁢            0                    +                                                                                              ⁢                  p          ⁢                                          ⁢          15          ×          p          ⁢                                          ⁢          14          ×          …          ×          p          ⁢                                          ⁢          2          ×          g          ⁢                                          ⁢          1                                                                                              ⁢                  ⋮          +                                                                                              ⁢                              p            ⁢                                                  ⁢            15            ×            g            ⁢                                                  ⁢            14                    +                                                                                              ⁢                  g          ⁢                                          ⁢          15                                                
Here, symbols pi and gi represent the carry propagation signal and carry generating signal of the (i+1)th digit, respectively, and they are represented by the following equations:
[Mathematical Equation 3]pi=ai⊕bi  (4)gi=ai×bi  (5)
Carry generating signal output circuits 1, 2, 3, 4 generate carry generating signals G3_0, G7_4, G11_8, G15_12, respectively.
With regard to carry generating signal G(j+3)_j (where j represents one of the integers 0, 4, 8 or 12), when 4-bit input data [aj, . . . a(j+3)] and [bj, . . . b(j+3)] are added, it is a signal indicating whether carry signal c(j+3) to the more significant digit becomes “1,” independent of carry signal C(j−1) (or CIN when j=0) from the less significant digit with respect to said 4 bits. When said signal is “1,” carry signal c(j+3) becomes “1” independent of the carry from the less significant digit. Carry generating signal G(j+3)_j is represented by the following equation:
[Mathematical Equation 4]
                                          G            ⁡                          (                              j                +                3                            )                                ⁢          _j                =                                            p              ⁡                              (                                  j                  +                  3                                )                                      ×                          p              ⁡                              (                                  j                  +                  2                                )                                      ×                          p              ⁡                              (                                  j                  +                  1                                )                                      ×            g            ⁢                                                  ⁢            j                    +                                    p              ⁡                              (                                  j                  +                  3                                )                                      ×                          p              ⁡                              (                                  j                  -                  2                                )                                      ×                          g              ⁡                              (                                  j                  +                  1                                )                                              +                                    p              ⁡                              (                                  j                  +                  3                                )                                      ×                          g              ⁡                              (                                  j                  +                  2                                )                                              +                      g            ⁡                          (                              j                +                3                            )                                                          (        6        )            
Carry propagation signal output circuits 5, 6, 7, 8 generate carry propagation signals P3_0, P7_4, P11_8, and P15_12, respectively. With regard to carry propagation signal P(j+3)_j (where j is one of the integers 0, 4, 8, or 12), when 4-bit input data [aj, . . . a(j+3)] and [bj, . . . b(j+3)] are added, it is a signal indicating whether carry signal c(j+3) to the more significant digit changes, depending on carry signal C(j−1) (or CIN when j=0) from the less significant digit with respect to said 4 bits. When said signal is “1,” carry signal c(j+3) changes to “1” or “0,” depending on the carry from the less significant digit.
Carry propagation signal P(j+3)_j is represented by the following equation:
[Mathematical Equation 5]P(j+3)—j=p(j+3)×p(j+2)×p(j+1)×pj  (7)
Carry propagation signal output circuits 9, 10 generate carry propagation signals P11_0 and P15_0, respectively. Carry propagation signals P11_0 and P15_0 are represented by the following equations, respectively:
[Mathematical Equation 6]
                                                                        P11_                ⁢                0                            =                              P11_                ⁢                8                ×                P7_                ⁢                4                ×                P3_                ⁢                0                                                                                        =                              p                ⁢                                                                  ⁢                11                ×                p                ⁢                                                                  ⁢                10                ×                …                ×                p                ⁢                                                                  ⁢                0                                                                        (        8        )                                                                                    P15_                ⁢                0                            =                              P15_                ⁢                12                ×                P11_                ⁢                8                ×                P7_                ⁢                4                ×                P3_                ⁢                0                                                                                        =                              p                ⁢                                                                  ⁢                15                ×                p                ⁢                                                                  ⁢                14                ×                …                ×                p                ⁢                                                                  ⁢                0                                                                        (        9        )            
Carry generating signal output circuits 11, 12 generate carry generating signals G11_0 and G15_0, respectively. Carry generating signals G11_0 and G15_0 are represented by the following equations, respectively:
                    [                  Mathematical          ⁢                                          ⁢          equation          ⁢                                          ⁢          7                ]                                                                      G11_          ⁢          0                =                              P11_            ⁢            8            ×            P7_            ⁢            4            ×            G3_            ⁢            0                    +                                    (        10        )                                                          ⁢                              P11_            ⁢            8            ×            G7_            ⁢            4                    +                                                                                              ⁢                  G11_          ⁢          8                                                                                              ⁢                  =                                    p              ⁢                                                          ⁢              11              ×              …              ×              p              ⁢                                                          ⁢              1              ×              g              ⁢                                                          ⁢              0                        +                                                                                                        ⁢                  p          ⁢                                          ⁢          11          ×          …          ×          p          ⁢                                          ⁢          2          ×          g          ⁢                                          ⁢          1                                                                                              ⁢                  ⋮          +                                                                                              ⁢                              p            ⁢                                                  ⁢            11            ×            g            ⁢                                                  ⁢            10                    +                                                                                              ⁢                  g          ⁢                                          ⁢          11                                                                              G15_          ⁢          0                =                              P15_            ⁢            12            ×            P11_            ⁢            8            ×            P7_            ⁢            4            ×            G3_            ⁢            0                    +                                    (        11        )                                                          ⁢                              P15_            ⁢            12            ×            P11_            ⁢            8            ×            G7_            ⁢            4                    +                                                                                              ⁢                              P15_            ⁢            12            ×            G11_            ⁢            8                    +                                                                                              ⁢                  G15_          ⁢          12                                                                                              ⁢                  =                                    p              ⁢                                                          ⁢              15              ×              …              ×              p              ⁢                                                          ⁢              1              ×              g              ⁢                                                          ⁢              0                        +                                                                                                        ⁢                  p          ⁢                                          ⁢          15          ×          …          ×          p          ⁢                                          ⁢          2          ×          g          ⁢                                          ⁢          1                                                                                              ⁢                  ⋮          +                                                                                              ⁢                              p            ⁢                                                  ⁢            15            ×            g            ⁢                                                  ⁢            14                    +                                                                                              ⁢                  g          ⁢                                          ⁢          15                                                
Here, by substituting equations 8 and 10 into equation 2, one obtains carry signal c11 represented by the following equation:
[Mathematical Equation 8]c11=P11—0×CIN+G11—0  (12)
Also, by substituting equations 9 and 11 into equation 3, one obtains carry signal C15 represented by the following equation:
[Mathematical Equation 9]c15=P15—0×CIN+G15—0  (3)
Selector 13 selects and outputs carry generating signal G11_0 when carry propagation signal P11_0 is “0,” and it selects and outputs carry signal CIN when carry propagation signal P11_0 is “1.” When carry propagation signal P11_0 becomes “1,” all the carry generating signals g0-g11 become “0,” and carry generating signal G11_0 becomes “0.” Consequently, the output signal of selector 13 becomes equal to carry signal c11 shown in equation 12.
Selector 14 selects and outputs carry generating signal G15_0 when carry propagation signal P15_0 is “0,” and it selects and outputs carry signal CIN when carry propagation signal P15_0 is “1.” Just as was explained above, when carry propagation signal P15_0 becomes “1,” carry generating signal G15_0 becomes “0,” and the output signal of selector 14 becomes equal to carry signal c15 shown in equation 13.
CSA15 computes beforehand the addition value for each of the 13th-16th digits when carry signal c11 is “1” and “0,” and from the two sets of computed addition values, the addition values selected corresponding to the value of carry signal c11 are output as addition results s12-s15. Also, just as in the case of the 15th carry, CSA15 selects one of the two pre-computed values corresponding to the value of carry signal c11, and outputs it as carry signal c14.
Exclusive-NOR circuit 16 computes the exclusive-NOR of carry signal c14 output from CSA15 and carry signal c15 output from selector 14. From the relationship of equation 1, the result of the operation of exclusive-NOR circuit 16 becomes overflow detection signal OVF16.
FIG. 13 is a block diagram illustrating an example of a circuit constitution for the output of carry signal C15A to the 17th digit. The same reference numbers are adopted as those in FIG. 12. Selector 17 selects and outputs carry signal Cdual input from the outside when dual mode assigning signal Mdual is “1,” and when Mdual is “0,” it selects and outputs carry signal c15 of the less significant 16 digits generated in the circuit shown in FIG. 12. The output signal of selector 17 becomes carry signal C15A to the 17th digit.
FIG. 14 is a block diagram illustrating an example of a circuit constitution for generating overflow detection signal OVF. The circuit shown in FIG. 14 has CSA 18, AND circuit 19, NOR circuit 20, OR circuit 21 and selectors 22 and 23. The circuit shown in FIG. 14 computes overflow detection signal OVF40 of the 40-bit mode and overflow detection signal OVF32 of the 32-bit mode, respectively.
Overflow detection signal OVF40 is a signal that is “0” when overflow occurs in the addition result for input data in the two's complement form, with the 40th digit being taken as the sign digit, and it is “1” when overflow does not occur. It is represented by the following equation:
[Mathematical Equation 10]OVF40= c38⊖c39  (14)
Also, overflow detection signal OVF32 is a signal that is “0” when overflow occurs in the addition result for input data in the two's complement form with the 32nd digit being taken as the sign digit, and it is “1” when overflow does not occur. It is represented by the following equation:
[Mathematical Equation 11]OVF32=(s31×. . . ×s39)+ (s31 +. . . +s39)  (15)
As can be seen from equation 15, in the 32-bit mode, overflow occurs when addition results s31-s39 are neither all “1” nor all “0.” For the situations when carry signal c30 is “1” and “0,” CSA18 computes beforehand the addition values of the various digits from the 32nd-40th digits, and from the two sets of the addition values computed, the addition values selected corresponding to carry signal c30 are output as addition results s31-s39. Together with said addition values, the pre-computed carries of the 39th digit and 40th digit are used, and when carry signal c30 is “0” and “1,” signals SC0 and SC1 for predicting whether overflow of the 40-bit mode occurs are respectively computed.
When carry signal c30 is “0,” the computed carry values of the 39th digit and 40th digit are taken as carry signals c38_0 and c39_0, respectively, and when carry signal c30 is “1,” the computed carry values of the 39th digit and 40th digit are taken as c38_1 and c39_1, respectively. The overflow prediction signals SC0 and SC1 are respectively represented by the following equations:
[Mathematical Equation 12]SC0= c38—0⊖c39—0  (16)SC1= c38—1⊕c39—1  (17)
Selector 22 takes overflow prediction signals SC0 and SC1 computed by CSA 18 as inputs, outputting prediction signal SC0 when carry signal c30 is “0,” and prediction signal SC1 when carry signal c30 is “1.” The output signal is input to selector 23 as overflow detection signal OVF40. AND circuit 19 computes the AND of addition results s31-s39 computed by CSA 18. The result has a value equal to the first term on the right hand side of equation 15. NOR circuit 20 computes the NOR of addition results s31-s39 computed by CSA 18. This result has a value equal to the second term on the right-hand side of equation 15. OR circuit 21 computes the OR of the output signals of AND circuit 19 and NOR circuit 20. The result is input to selector 23 as overflow detection signal OVF32. Selector 23 selects one of the two input overflow detection signals OVF32 and OVF40 corresponding to mode assigning signal M40, and outputs it as overflow detection signal OVF.
In the circuit shown in FIG. 12, in order to increase the speed of generating carry signal c15 and overflow detection signal OVF16, the processes for generating the two carry signals c14 and c15 are performed in parallel. That is, carry look-ahead circuits (9, 11) for generating carry signal c14 and carry look-ahead circuits (10, 12) for generating carry signal c15 are independent from each other. Consequently, the capacitive load rises for the former-stage carry look-ahead circuits (1-8) for driving said circuits, the power consumption increases, and the speed of overflow detection signal OVF16 decreases. This is undesirable.
In the circuit shown in FIG. 13, carry generating signal G15_0 that is required to have the highest speed among the signals that generate carry signal c15A has to pass through the two stages of selectors (14, 17) before reaching the output. Consequently, the generation of carry signal c15A becomes slower, and the operating speed drops. This is undesirable.
In addition, in the circuit shown in FIG. 14, after the arrival of carry signal c30 as the most delayed signal, the addition results s31-s39, output signal 0 of AND circuit 19 and NOR circuit 20, the overflow detection signal OVF32 and overflow detection signal OVF are established sequentially. In other words, because the path of carry signal c30 that requires a high speed is long, the speed of overflow detection signal OVF decreases, and this is undesirable.
A general object of the present invention is to solve the problems of the prior art by providing a type of adder that can detect the generation of overflow at high speed.